home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / docs / misc / ConcNews.lha / news / amiga.programming / comp.sys.amiga.programmer_5345_000025.msg < prev    next >
Encoding:
Text File  |  1994-11-27  |  3.5 KB  |  130 lines
  1. Newsgroups: comp.sys.amiga.programmer
  2. Path: dd.chalmers.se!news.chalmers.se!sunic!pipex!howland.reston.ans.net!vixen.cso.uiuc.edu!sdd.hp.com!col.hp.com!news.dtc.hp.com!hplextra!hplb!hpwin052!hpqmoea!neilg
  3. From: neilg@hpqtdya.sqf.hp.com (Neil Gall)
  4. Subject: Re: Public implementation of Lists/Nodes?
  5. Sender: news@hpqmoea.sqf.hp.com (SQF News Admin)
  6. Message-ID: <CKLMu3.HL1@hpqmoea.sqf.hp.com>
  7. Date: Wed, 2 Feb 1994 13:30:03 GMT
  8. References: <BEUST.94Feb2114402@indri.inria.fr>
  9. Nntp-Posting-Host: hpqto014.sqf.hp.com
  10. Organization: Hewlett-Packard LTD, South Queensferry, Scotland
  11. X-Newsreader: TIN [version 1.1 PL8.8]
  12. Lines: 116
  13.  
  14. Cedric Beust (beust@indri.inria.fr) wrote:
  15.  
  16. :       I was wondering if someone had re-written the functions
  17. :       NewList(), AddTail(), etc... in order to be able to use them in
  18. :       a non-Amiga environment? I really like them and
  19. :       would like to use the same API in my work (and avoid
  20. :       implementing them personally of course :-)).
  21.  
  22. I implemented Exec-style lists in C++ for a project I was working on
  23. about three months ago.  They're really easy to implement once you
  24. work out what's going on.  Here's a solution in C:
  25.  
  26. You need to define the structures:
  27.  
  28. struct List
  29. {
  30.     struct Node *Head;
  31.     struct Node *Tail;
  32.     struct Node *TailPred;
  33. };
  34.  
  35. struct Node
  36. {
  37.     struct Node *Succ;
  38.     struct Node *Pred;
  39. };
  40.  
  41. And the following functions:
  42.  
  43. void NewList(struct List *list)
  44. {
  45.     list->Head = (struct Node *)&list->Tail;
  46.     list->Tail = NULL;
  47.     list->TailPred = (struct Node *)list;
  48. }
  49.  
  50. void AddHead(struct List *list,struct Node *node)
  51. {
  52.     node->Succ=list->Head;
  53.     node->Pred=(struct Node *)list;
  54.     list->Head->Pred=node;
  55.     list->Head=node;
  56. }
  57.  
  58. void AddTail(struct List *list,struct Node *node)
  59. {
  60.     node->Succ=(struct Node *)&list->Tail;
  61.     node->Pred=list->TailPred;
  62.     list->TailPred->Succ=node;
  63.     list->TailPred=node;
  64. }
  65.  
  66. struct Node *RemHead(struct List *list)
  67. {
  68.     struct Node *node=NULL;
  69.  
  70.     if (list->Head->Succ)
  71.     {    
  72.         node=list->Head;
  73.     
  74.     list->Head->Succ->Pred=(struct Node *)list;
  75.     list->Head=list->Head->Succ;
  76.     }
  77.     
  78.     return node;
  79. }
  80.  
  81. struct Node *RemTail(struct List *list)
  82. {
  83.     struct Node *node=NULL;
  84.     
  85.     if (list->TailPred->Pred)
  86.     {
  87.         node=list->TailPred;
  88.     
  89.         list->TailPred->Pred->Succ=list->TailPred;
  90.         list->TailPred=list->TailPred->Pred;
  91.     }
  92.     
  93.     return node;
  94. }
  95.  
  96. void Remove(struct Node *node)
  97. {
  98.     node->Succ->Pred=node->Pred;
  99.     node->Pred->Succ=node->Succ;
  100. }
  101.  
  102. That's all I can remember at the moment.  AddHead() can be generalised
  103. to get Insert(list,node,pred), and Enqueue() is done simply by scanning
  104. the list for a node with the right priority (you have to include a
  105. priority field into the node structure).
  106.  
  107. In C++, these were really good.  List and Node were classes, and everything
  108. which was "listable" was derived from Node, inheriting all the Node methods.
  109. If I remember correctly, most of the operations were List methods, so say
  110. you had a list called foo, and wanted to add a node bar, you did
  111.  
  112.     foo.AddTail(bar);
  113.     
  114. Then I overloaded << to mean AddTail(), so you could say
  115.  
  116.     foo << bar;
  117.     
  118. Of course this returned foo, so you could say
  119.  
  120.     foo << bar << baz << boz;
  121.     
  122. to add a number of objects to the tail of the list.  Similarly you
  123. could use >> to mean RemHead, thus implementing a queue with
  124. operators.
  125.  
  126. --
  127. Neil Gall                Queensferry Telecoms Operation
  128. neilg@hpqtdya.sqf.hp.com        Hewlett-Packard Ltd.
  129. 031-331-7895                South Queensferry, Scotland
  130.